//1. 使用哈希表（空间换时间）--------时间复杂度：O(n),空间复杂度：O(n)
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==nullptr) 
            return nullptr;
        unordered_map<Node*, Node*> deepcopy;
        Node* act1 = head;
        while(act1) {
            deepcopy[act1] = new Node(act1->val);
            // 键：值 = 原来的head节点：新申请的head节点(val),无 next、random
            //遍历存储所有的head
            act1 = act1->next;
        }
        Node* act2 = head;
        while(act2) {
            deepcopy[act2]->next =  deepcopy[act2->next];
            deepcopy[act2]->random =  deepcopy[act2->random];
            act2 = act2->next;
        }
        return deepcopy[head];
    }
};

//2.迭代 + 节点拆分------空间复杂度：O(1)
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;

        // 第一步：在原节点后插入拷贝节点
        Node* curr = head;
        while (curr) {
            Node* copy = new Node(curr->val);
            copy->next = curr->next;
            curr->next = copy;
            curr = copy->next;
        }

        // 第二步：设置拷贝节点的 random 指针
        curr = head;
        while (curr) {
            if (curr->random)
                curr->next->random = curr->random->next; ///原节点 A 的 random 指向节点 T，那么它的拷贝节点 A' 的 random 应该指向 T'。而 T' 是 T 的后面那个节点
            curr = curr->next->next;
        }

        // 第三步：拆分原链表和拷贝链表
        curr = head;
        Node* newHead = head->next;
        while (curr) {
            Node* copy = curr->next;
            curr->next = copy->next;
            if (copy->next)
                copy->next = copy->next->next;
            curr = curr->next;
        }

        return newHead;
    }
};



